﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Web;
using System.IO;
using System.Text;
using System.Runtime.Serialization.Json;
using System.Web.Script.Serialization;

namespace TravelManagement
{
    /// <summary>
    /// Summary description for ShortestPathCalculator
    /// </summary>
    /// what is ashx..http://stackoverflow.com/questions/619697/what-are-the-benefits-of-an-ashx-handler-file-in-asp-net
    /// 
    /// how to do it.. http://www.dotnetperls.com/ashx
    /// http://stackoverflow.com/questions/5071682/receiving-post-data-in-ashx-file
    /// to convert json into c# object http://stackoverflow.com/questions/4611031/convert-json-string-to-c-sharp-object
    /// 
    public class ShortestPathCalculator : IHttpHandler
    {

        public void ProcessRequest(HttpContext context)
        {

            StreamReader reader = new StreamReader(context.Request.InputStream, context.Request.ContentEncoding);
            string input = reader.ReadToEnd();

            var deserializer = new JavaScriptSerializer();

            RootObject distanceMatrix = deserializer.Deserialize(input, typeof(RootObject)) as RootObject;

            int nodeCount = distanceMatrix.rows.Length;

            List<short> arrayOfNodes = new List<short>();

            for (short i = 1; i < nodeCount; i++)
            {
                arrayOfNodes.Add(i);
            }

            List<List<short>> combinations = GenerateAllCombinations(arrayOfNodes);

            int shortestPath = Int32.MaxValue;
            List<short> shortestPathCombination = null;

            foreach (List<short> combination in combinations)
            {
                combination.Insert(0, 0);
                combination.Insert(nodeCount, 0);

                int pathLength = GetPathLength(combination, distanceMatrix);
                if (pathLength < shortestPath)
                {
                    shortestPathCombination = combination;
                    shortestPath = pathLength;
                }

            }


            var serializer = new JavaScriptSerializer();
            string output = serializer.Serialize(shortestPathCombination);

            context.Response.ContentType = "text/plain";
            context.Response.StatusCode = 200;
            context.Response.Write(output);

        }

        private int GetPathLength(List<short> combination, RootObject distanceMatrix)
        {
            int length = 0;

            for (int i = 0; i < combination.Count-1; i++)
            {
                int source = combination[i];
                int destination = i + 1;
                if (destination == combination.Count - 1)
                {
                    destination = combination[0];
                }
                else
                {
                    destination = combination[i + 1];
                }

                length = length + distanceMatrix.rows[source].elements[destination].distance.value;
            }

            return length;
        }

        public bool IsReusable
        {
            get
            {
                return false;
            }
        }

        private List<List<T>> GenerateAllCombinations<T>(List<T> array)
        {
            List<List<T>> allLists = new List<List<T>>();
            List<T> initialList = new List<T>();
            initialList.Add(array[0]);
            allLists.Add(initialList);

            //i is the next element to be inserted.
            for (short i = 1; i < array.Count; i++)
            {
                List<List<T>> newAllLists = new List<List<T>>();

                foreach (List<T> existingList in allLists)
                {
                    List<List<T>> tempAllLists = new List<List<T>>();
                    for (int j = 0; j <= existingList.Count; j++)
                    {
                        List<T> newList = new List<T>();
                        newList.AddRange(existingList);
                        newList.Insert(j, array[i]);
                        tempAllLists.Add(newList);
                    }
                    newAllLists.AddRange(tempAllLists);
                    allLists = newAllLists;
                }

                GC.Collect();
            }
            return allLists;
        }

    }
}